package com.peng.leetcode.dynamic;

/**
 * LongestValidParentheses
 *
 * 32. 最长有效括号
 *
 * @author: lupeng6
 * @create: 2021/2/4 15:26
 */
public class LongestValidParentheses {

    public static void main(String[] args) {
        String s = ")()())";
//        String s = "))()(())";
//        String s = "())";
//        String s = "(()())";
        System.out.println(new LongestValidParentheses().longestValidParentheses(s));
    }

    /**
     * 动态规划解最长字符串
     * s[i] == ')' && s[i - 1] == '('
     *      dp[i] = dp[i - 2] + 2
     * s[i] == ')' && s[i - 1] == ')' && dp[i - 1] > 0 && s[i - dp[i - 1] - 1] == '('
     *      dp[i] = dp[i - 1] + 2 + dp[i - dp[i - 1] - 2]
     *
     * @author lupeng6
     * @date 2021/2/4 15:27
     */
    public int longestValidParentheses(String s) {
        int maxLen = 0;
        int[] dp = new int[s.length()];
        for (int i = 1; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == ')') {
                if (s.charAt(i - 1) == '(') {
                    // 当i == 3 也就是说第四个元素才可能存在 dp[i - 2] > 0
                    dp[i] = (i > 2 ? dp[i - 2] : 0) + 2;
                }
                if (s.charAt(i - 1) == ')' && dp[i - 1] > 0) {
                    if ((i - dp[i - 1] - 1) >= 0 && s.charAt(i - dp[i - 1] - 1) == '(') {
                        int iLen = dp[i - 1] + 2;
                        if ((i - dp[i - 1] - 2) >= 0) {
                            iLen += dp[i - dp[i - 1] - 2];
                        }
                        dp[i] =iLen;
                    }
                }
            }

            maxLen = Math.max(maxLen, dp[i]);
        }
        return maxLen;
    }
}
